home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / dev / c / qtools0.2-src.lha / src / libqbuild / rad.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-07-15  |  44.7 KB  |  1,856 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. vec3_t *texreflectivity;
  5. vec3_t *radiosity;
  6. vec3_t *illumination;
  7. struct patch **facepatches;
  8. struct entity **faceentity;
  9. struct patch *patches;
  10. int numpatches = 0;
  11. struct dplane_t *backplanes;
  12. int fakeplanes;
  13. int *leafparents;
  14. int *nodeparents;
  15. float subdiv = 64;
  16. struct directlight **directlights;
  17. struct facelight *facelights;
  18. int numdlights = 0;
  19. int numbounce = 8;
  20. bool dumppatches;
  21. int junk;
  22. float ambient = 0;
  23. float maxlight = 196;
  24. float lightscale = 1.0;
  25. float direct_scale = 0.4;
  26. float entity_scale = 1.0;
  27.  
  28. extern struct tnode *tnodes, *tnode_p;
  29. int TestLine_r(register int node, vec3_t start, vec3_t stop)
  30. {
  31.   struct tnode *tnode;
  32.   float front, back;
  33.   vec3_t mid;
  34.   float frac;
  35.   int side;
  36.   int r;
  37.  
  38.   if (node & (1 << 31))
  39.     return node & ~(1 << 31);                    /* leaf node */
  40.  
  41.   tnode = &tnodes[node];
  42.   switch (tnode->type) {
  43.     case PLANE_X:
  44.       front = start[0] - tnode->dist;
  45.       back = stop[0] - tnode->dist;
  46.       break;
  47.     case PLANE_Y:
  48.       front = start[1] - tnode->dist;
  49.       back = stop[1] - tnode->dist;
  50.       break;
  51.     case PLANE_Z:
  52.       front = start[2] - tnode->dist;
  53.       back = stop[2] - tnode->dist;
  54.       break;
  55.     default:
  56.       front = DotProduct(start, tnode->normal) - tnode->dist;
  57.       back = DotProduct(stop, tnode->normal) - tnode->dist;
  58.       /*
  59.        * front = (start[0] * tnode->normal[0] + start[1] * tnode->normal[1] + start[2] * tnode->normal[2]) - tnode->dist;
  60.        * back = (stop[0] * tnode->normal[0] + stop[1] * tnode->normal[1] + stop[2] * tnode->normal[2]) - tnode->dist;
  61.        */
  62.       break;
  63.   }
  64.  
  65.   if (front >= -ON_EPSILON && back >= -ON_EPSILON)
  66.     return TestLine_r(tnode->children[0], start, stop);
  67.  
  68.   if (front < ON_EPSILON && back < ON_EPSILON)
  69.     return TestLine_r(tnode->children[1], start, stop);
  70.  
  71.   side = front < 0;
  72.  
  73.   frac = front / (front - back);
  74.  
  75.   mid[0] = start[0] + (stop[0] - start[0]) * frac;
  76.   mid[1] = start[1] + (stop[1] - start[1]) * frac;
  77.   mid[2] = start[2] + (stop[2] - start[2]) * frac;
  78.  
  79.   if ((r = TestLine_r(tnode->children[side], start, mid)))
  80.     return r;
  81.   else
  82.     return TestLine_r(tnode->children[!side], mid, stop);
  83. }
  84.  
  85. /*
  86.  * =============
  87.  * CollectLight
  88.  * =============
  89.  */
  90. float CollectLight(void)
  91. {
  92.   int i, j;
  93.   struct patch *patch;
  94.   vec_t total;
  95.  
  96.   total = 0;
  97.  
  98.   for (i = 0, patch = patches; i < numpatches; i++, patch++) {
  99.     /* skys never collect light, it is just dropped */
  100.     if (patch->sky) {
  101.       VectorClear(radiosity[i]);
  102.       VectorClear(illumination[i]);
  103.       continue;
  104.     }
  105.  
  106.     for (j = 0; j < 3; j++) {
  107.       patch->totallight[j] += illumination[i][j] / patch->area;
  108.       radiosity[i][j] = illumination[i][j] * patch->reflectivity[j];
  109.     }
  110.  
  111.     total += radiosity[i][0] + radiosity[i][1] + radiosity[i][2];
  112.     VectorClear(illumination[i]);
  113.   }
  114.  
  115.   return total;
  116. }
  117.  
  118. /*
  119.  * =============
  120.  * ShootLight
  121.  * 
  122.  * Send light out to other patches
  123.  * Run multi-threaded
  124.  * =============
  125.  */
  126. void ShootLight(register int patchnum)
  127. {
  128.   int k, l;
  129.   struct transfer *trans;
  130.   int num;
  131.   struct patch *patch;
  132.   vec3_t send;
  133.  
  134.   /*
  135.    * this is the amount of light we are distributing
  136.    * prescale it so that multiplying by the 16 bit
  137.    * transfer values gives a proper output value
  138.    */
  139.   for (k = 0; k < 3; k++)
  140.     send[k] = radiosity[patchnum][k] / 0x10000;
  141.   patch = &patches[patchnum];
  142.  
  143.   trans = patch->transfers;
  144.   num = patch->numtransfers;
  145.  
  146.   for (k = 0; k < num; k++, trans++) {
  147.     for (l = 0; l < 3; l++)
  148.       illumination[trans->patch][l] += send[l] * trans->transfer;
  149.   }
  150. }
  151.  
  152. /*
  153.  * =============
  154.  * BounceLight
  155.  * =============
  156.  */
  157. void BounceLight(void)
  158. {
  159.   int i, j;
  160.   float added;
  161.   struct patch *p;
  162.  
  163.   for (i = 0; i < numpatches; i++) {
  164.     p = &patches[i];
  165.     for (j = 0; j < 3; j++) {
  166. /*                      p->totallight[j] = p->samplelight[j]; */
  167.       radiosity[i][j] = p->samplelight[j] * p->reflectivity[j] * p->area;
  168.     }
  169.   }
  170.  
  171.   for (i = 0; i < numbounce; i++) {
  172.     for (j = 0; j < numpatches; j++)
  173.       ShootLight(j);
  174.  
  175.     added = CollectLight();
  176.     mprintf("    - bounce %i\n%5i added\n", i, added);
  177.   }
  178. }
  179.  
  180. void ClearLBounds(vec3_t mins, vec3_t maxs)
  181. {
  182.   mins[0] = mins[1] = mins[2] = 99999;
  183.   maxs[0] = maxs[1] = maxs[2] = -99999;
  184. }
  185.  
  186. void AddPointToBounds(vec3_t v, vec3_t mins, vec3_t maxs)
  187. {
  188.   int i;
  189.   vec_t val;
  190.  
  191.   for (i = 0; i < 3; i++) {
  192.     val = v[i];
  193.     if (val < mins[i])
  194.       mins[i] = val;
  195.     if (val > maxs[i])
  196.       maxs[i] = val;
  197.   }
  198. }
  199.  
  200. /*
  201.  * ===================================================================
  202.  * 
  203.  * TEXTURE LIGHT VALUES
  204.  * 
  205.  * ===================================================================
  206.  */
  207.  
  208. vec_t ColorNormalize(vec3_t in, vec3_t out)
  209. {
  210.   float max;
  211.  
  212.   max = in[0];
  213.   if (in[1] > max)
  214.     max = in[1];
  215.   if (in[2] > max)
  216.     max = in[2];
  217.  
  218.   if (max != 0)
  219.     VectorScale(in, 1.0 / max, out);
  220.  
  221.   return max;
  222. }
  223.  
  224. /*
  225.  * ======================
  226.  * CalcTextureReflectivity
  227.  * ======================
  228.  */
  229. void CalcTextureReflectivity(__memBase)
  230. {
  231.   int i, j;
  232.   struct rgb *palette;
  233.   struct dmiptexlump_t *l = (struct dmiptexlump_t *)bspMem->shared.quake1.dtexdata;
  234.  
  235.   if (!(palette = GetPalette()))
  236.     Error(failed_fileopen, "palette");
  237.  
  238.   /* allways set index 0 even if no textures */
  239.   texreflectivity[0][0] = 0.5;
  240.   texreflectivity[0][1] = 0.5;
  241.   texreflectivity[0][2] = 0.5;
  242.  
  243.   for (i = 0; i < bspMem->shared.quake1.numtexinfo; i++) {
  244.     struct texinfo *curtex = &bspMem->shared.quake1.texinfo[i];
  245.  
  246.     /* see if an earlier texinfo allready got the value */
  247.     for (j = 0; j < i; j++) {
  248.       if (curtex->miptex == bspMem->shared.quake1.texinfo[j].miptex) {
  249.     VectorCopy(texreflectivity[j], texreflectivity[i]);
  250.     break;
  251.       }
  252.     }
  253.  
  254.     if (j == i) {
  255.       struct mipmap *mt = (struct mipmap *)(l->dataofs[curtex->miptex] + (long int)l);
  256.       int texels = mt->width * mt->height;
  257.       unsigned char texel;
  258.       unsigned char *body = (unsigned char *)mt + mt->offsets[MIPMAP_0];
  259.       int color[3] =
  260.       {0, 0, 0};
  261.       float scale;
  262.  
  263.       for (j = 0; j < texels; j++) {
  264.     texel = *body++;
  265.     color[0] += palette[texel].r;
  266.     color[1] += palette[texel].g;
  267.     color[2] += palette[texel].b;
  268.       }
  269.  
  270.       for (j = 0; j < 3; j++) {
  271.     float r = color[j] / texels / 255.0;
  272.  
  273.     texreflectivity[i][j] = r;
  274.       }
  275.  
  276.       mprintf("%s has a reflectivity of (%f,%f,%f)\n", mt->name, texreflectivity[i][0], texreflectivity[i][1], texreflectivity[i][2]);
  277.  
  278.       /*
  279.        * scale the reflectivity up, because the textures are
  280.        * so dim
  281.        */
  282.       scale = ColorNormalize(texreflectivity[i], texreflectivity[i]);
  283.       if (scale < 0.5) {
  284.     scale *= 2;
  285.     VectorScale(texreflectivity[i], scale, texreflectivity[i]);
  286.       }
  287.     }
  288.   }
  289. }
  290.  
  291. /*
  292.  * ===================
  293.  * DecompressVis
  294.  * ===================
  295.  */
  296. void DecompressVis(__memBase, register unsigned char *in, register unsigned char *decompressed)
  297. {
  298.   int c;
  299.   int row;
  300.   unsigned char *out;
  301.  
  302.   row = (bspMem->shared.quake1.numleafs + 7) >> 3;
  303.   out = decompressed;
  304.  
  305.   do {
  306.     if (*in) {
  307.       *out++ = *in++;
  308.       continue;
  309.     }
  310.  
  311.     c = in[1];
  312.     in += 2;
  313.     while (c) {
  314.       *out++ = 0;
  315.       c--;
  316.     }
  317.   } while (out - decompressed < row);
  318. }
  319.  
  320. int PointInLeafNum(__memBase, vec3_t point)
  321. {
  322.   int nodenum;
  323.   vec_t dist;
  324.   struct dnode_t *node;
  325.   struct dplane_t *plane;
  326.  
  327.   nodenum = 0;
  328.   while (nodenum >= 0) {
  329.     node = &bspMem->shared.quake1.dnodes[nodenum];
  330.     plane = &bspMem->shared.quake1.dplanes[node->planenum];
  331.     dist = DotProduct(point, plane->normal) - plane->dist;
  332.     if (dist > 0)
  333.       nodenum = node->children[0];
  334.     else
  335.       nodenum = node->children[1];
  336.   }
  337.  
  338.   return -nodenum - 1;
  339. }
  340.  
  341. bool PvsForOrigin(__memBase, vec3_t org, register unsigned char *pvs)
  342. {
  343.   if (!bspMem->shared.quake1.visdatasize) {
  344.     __memset(pvs, 255, (bspMem->shared.quake1.numleafs + 7) >> 3);
  345.   }
  346.   else {
  347.     struct dleaf_t *leaf = &bspMem->shared.quake1.dleafs[PointInLeafNum(bspMem, org)];
  348.  
  349.     DecompressVis(bspMem, bspMem->shared.quake1.dvisdata + leaf->visofs, pvs);
  350.   }
  351.  
  352.   return TRUE;
  353. }
  354.  
  355. /*
  356.  * =============
  357.  * MakeBackplanes
  358.  * =============
  359.  */
  360. void MakeBackPlanes(__memBase)
  361. {
  362.   int i;
  363.  
  364.   for (i = 0; i < bspMem->shared.quake1.numplanes; i++) {
  365.     backplanes[i].dist = -bspMem->shared.quake1.dplanes[i].dist;
  366.     VectorNegateTo(bspMem->shared.quake1.dplanes[i].normal, backplanes[i].normal);
  367.   }
  368. }
  369.  
  370. /*
  371.  * =============
  372.  * MakeParents
  373.  * =============
  374.  */
  375. void MakeParents(__memBase, register int nodenum, register int parent)
  376. {
  377.   int i, j;
  378.   struct dnode_t *node;
  379.  
  380.   nodeparents[nodenum] = parent;
  381.   node = &bspMem->shared.quake1.dnodes[nodenum];
  382.  
  383.   for (i = 0; i < 2; i++) {
  384.     j = node->children[i];
  385.     if (j < 0)
  386.       leafparents[-j - 1] = nodenum;
  387.     else
  388.       MakeParents(bspMem, j, nodenum);
  389.   }
  390. }
  391.  
  392. /*
  393.  * =============
  394.  * MakePatchForFace
  395.  * =============
  396.  */
  397.  
  398. bool IsSky(__memBase, register struct dface_t *f)
  399. {
  400.   struct texinfo *tx;
  401.   struct mipmap *mt;
  402.   struct dmiptexlump_t *l = (struct dmiptexlump_t *)bspMem->shared.quake1.dtexdata;
  403.  
  404.   tx = &bspMem->shared.quake1.texinfo[f->texinfo];
  405.   mt = (struct mipmap *)(l->dataofs[tx->miptex] + (long int)l);
  406.   if (!__strcmp(mt->name, "sky"))
  407.     return TRUE;
  408.   return FALSE;
  409. }
  410.  
  411. #define    MAX_PATCHES        4096
  412. float totalarea;
  413. void MakePatchForFace(__memBase, register int facenum, register struct winding *w)
  414. {
  415.   struct dface_t *f;
  416.   float area;
  417.   struct patch *patch;
  418.   struct dplane_t *pl;
  419.   int i;
  420.   vec3_t color;
  421.   struct dleaf_t *leaf;
  422.  
  423.   f = &bspMem->shared.quake1.dfaces[facenum];
  424.  
  425.   area = WindingArea(w);
  426.   totalarea += area;
  427.  
  428.   patch = &patches[numpatches];
  429.   if (numpatches == MAX_PATCHES)
  430.     Error("numpatches == MAX_PATCHES\n");
  431.   patch->next = facepatches[facenum];
  432.   facepatches[facenum] = patch;
  433.  
  434.   patch->winding = w;
  435.  
  436.   if (f->side)
  437.     patch->plane = &backplanes[f->planenum];
  438.   else
  439.     patch->plane = &bspMem->shared.quake1.dplanes[f->planenum];
  440.   if (faceoffset[facenum][0] || faceoffset[facenum][1] || faceoffset[facenum][2]) {    /* origin offset faces must create new planes */
  441.     if (bspMem->shared.quake1.numplanes + fakeplanes >= bspMem->shared.quake1.max_numplanes)
  442.       ExpandClusters(bspMem, LUMP_PLANES);
  443.     pl = &bspMem->shared.quake1.dplanes[bspMem->shared.quake1.numplanes + fakeplanes];
  444.     fakeplanes++;
  445.  
  446.     *pl = *(patch->plane);
  447.     pl->dist += DotProduct(faceoffset[facenum], pl->normal);
  448.     patch->plane = pl;
  449.   }
  450.  
  451.   WindingCenter(w, patch->origin);
  452.   VectorAdd(patch->origin, patch->plane->normal, patch->origin);
  453.   leaf = &bspMem->shared.quake1.dleafs[PointInLeafNum(bspMem, patch->origin)];
  454.   patch->cluster = leaf->visofs;
  455.   patch->area = area;
  456.   if (patch->area <= 1)
  457.     patch->area = 1;
  458.   patch->sky = IsSky(bspMem, f);
  459.  
  460.   VectorCopy(texreflectivity[f->texinfo], patch->reflectivity);
  461.  
  462.   /* non-bmodel patches can emit light */
  463.   if (facenum < bspMem->shared.quake1.dmodels[0].numfaces) {
  464.     VectorClear(patch->baselight);
  465.     ColorNormalize(patch->reflectivity, color);
  466.     for (i = 0; i < 3; i++)
  467.       patch->baselight[i] *= color[i];
  468.     VectorCopy(patch->baselight, patch->totallight);
  469.   }
  470.   numpatches++;
  471. }
  472.  
  473. /*
  474.  * =============
  475.  * MakePatches
  476.  * =============
  477.  */
  478. void MakePatches(__memBase)
  479. {
  480.   int i, j, k;
  481.   struct dface_t *f;
  482.   int start;
  483.   struct winding *w;
  484.   struct dmodel_t *mod;
  485.   struct entity *ent;
  486.  
  487.   mprintf("%5i faces\n", bspMem->shared.quake1.numfaces);
  488.  
  489.   for (i = 0; i < bspMem->shared.quake1.nummodels; i++) {
  490.     mod = &bspMem->shared.quake1.dmodels[i];
  491.     ent = FindEntityWithModel(bspMem, i);
  492.     /*
  493.      * bmodels with origin brushes need to be offset into their
  494.      * in-use position
  495.      */
  496.     start = mod->firstface;
  497.     for (j = start; j < start + mod->numfaces; j++) {
  498.       VectorCopy(ent->origin, faceoffset[j]);
  499.       faceentity[j] = ent;
  500.       f = &bspMem->shared.quake1.dfaces[j];
  501.       w = WindingFromFace(bspMem, f);
  502.       for (k = 0; k < w->numpoints; k++) {
  503.     VectorAdd(w->points[k], ent->origin, w->points[k]);
  504.       }
  505.       MakePatchForFace(bspMem, j, w);
  506.     }
  507.   }
  508.  
  509.   mprintf("%5i square feet\n", (int)(totalarea / 64));
  510. }
  511.  
  512. void CheckPatches(void)
  513. {
  514.   int i;
  515.   struct patch *patch;
  516.  
  517.   for (i = 0; i < numpatches; i++) {
  518.     patch = &patches[i];
  519.     if (patch->totallight[0] < 0 || patch->totallight[1] < 0 || patch->totallight[2] < 0)
  520.       Error("negative patch totallight\n");
  521.   }
  522. }
  523.  
  524. /*
  525.  * =============
  526.  * MakeTransfers
  527.  * 
  528.  * =============
  529.  */
  530. int total_transfer;
  531.  
  532. void MakeTransfers(__memBase, register int i)
  533. {
  534.   int j;
  535.   vec3_t delta;
  536.   vec_t dist, scale;
  537.   float trans;
  538.   int itrans;
  539.   struct patch *patch, *patch2;
  540.   float total;
  541.   struct dplane_t plane;
  542.   vec3_t origin;
  543.   float transfers[MAX_PATCHES], *all_transfers;
  544.   int itotal;
  545.   unsigned char pvs[(MAX_MAP_LEAFS + 7) / 8];
  546.   int cluster;
  547.  
  548.   patch = patches + i;
  549.   total = 0;
  550.  
  551.   VectorCopy(patch->origin, origin);
  552.   plane = *patch->plane;
  553.  
  554.   if (!PvsForOrigin(bspMem, patch->origin, pvs))
  555.     return;
  556.  
  557.   /*
  558.    * find out which patch2s will collect light
  559.    * from patch
  560.    */
  561.   all_transfers = transfers;
  562.   patch->numtransfers = 0;
  563.   for (j = 0, patch2 = patches; j < numpatches; j++, patch2++) {
  564.     transfers[j] = 0;
  565.  
  566.     if (j == i)
  567.       continue;
  568.  
  569.     /* check pvs bit */
  570.     if (!bspMem->shared.quake1.visdatasize) {
  571.       cluster = patch2->cluster;
  572.       if (cluster == -1)
  573.     continue;
  574.       if (!(pvs[cluster >> 3] & (1 << (cluster & 7))))
  575.     continue;                        /* not in pvs */
  576.     }
  577.  
  578.     /* calculate vector */
  579.     VectorSubtract(patch2->origin, origin, delta);
  580.     dist = VectorNormalize(delta);
  581.     if (!dist)
  582.       continue;                            /* should never happen */
  583.  
  584.     /* reletive angles */
  585.     scale = DotProduct(delta, plane.normal);
  586.     scale *= -DotProduct(delta, patch2->plane->normal);
  587.     if (scale <= 0)
  588.       continue;
  589.  
  590.     /* check exact tramsfer */
  591.     if (TestLine_r(0, patch->origin, patch2->origin))
  592.       continue;
  593.  
  594.     trans = scale * patch2->area / (dist * dist);
  595.  
  596.     if (trans < 0)
  597.       trans = 0;                        /* rounding errors... */
  598.  
  599.     transfers[j] = trans;
  600.     if (trans > 0) {
  601.       total += trans;
  602.       patch->numtransfers++;
  603.     }
  604.   }
  605.  
  606.   /*
  607.    * copy the transfers out and normalize
  608.    * total should be somewhere near PI if everything went right
  609.    * because partial occlusion isn't accounted for, and nearby
  610.    * patches have underestimated form factors, it will usually
  611.    * be higher than PI
  612.    */
  613.   if (patch->numtransfers) {
  614.     struct transfer *t;
  615.  
  616.     if (patch->numtransfers < 0 || patch->numtransfers > MAX_PATCHES)
  617.       Error("Weird numtransfers\n");
  618.     if (!(patch->transfers = (struct transfer *)tmalloc(patch->numtransfers * sizeof(struct transfer))))
  619.         Error(failed_memoryunsize, "transfer");
  620.  
  621.     /*
  622.      * normalize all transfers so all of the light
  623.      * is transfered to the surroundings
  624.      */
  625.     t = patch->transfers;
  626.     itotal = 0;
  627.     for (j = 0; j < numpatches; j++) {
  628.       if (transfers[j] <= 0)
  629.     continue;
  630.       itrans = transfers[j] * 0x10000 / total;
  631.       itotal += itrans;
  632.       t->transfer = itrans;
  633.       t->patch = j;
  634.       t++;
  635.     }
  636.   }
  637.  
  638.   /* don't bother locking around this.  not that important. */
  639.   total_transfer += patch->numtransfers;
  640. }
  641.  
  642. /*
  643.  * =============
  644.  * FreeTransfers
  645.  * =============
  646.  */
  647. void FreeTransfers(void)
  648. {
  649.   int i;
  650.  
  651.   for (i = 0; i < numpatches; i++) {
  652.     tfree(patches[i].transfers);
  653.     patches[i].transfers = NULL;
  654.   }
  655. }
  656.  
  657. /*
  658.  * =======================================================================
  659.  * 
  660.  * SUBDIVIDE
  661.  * 
  662.  * =======================================================================
  663.  */
  664.  
  665. void FinishSplit(__memBase, register struct patch *patch, register struct patch *newp)
  666. {
  667.   struct dleaf_t *leaf;
  668.  
  669.   VectorCopy(patch->baselight, newp->baselight);
  670.   VectorCopy(patch->totallight, newp->totallight);
  671.   VectorCopy(patch->reflectivity, newp->reflectivity);
  672.   newp->plane = patch->plane;
  673.   newp->sky = patch->sky;
  674.  
  675.   patch->area = WindingArea(patch->winding);
  676.   newp->area = WindingArea(newp->winding);
  677.  
  678.   if (patch->area <= 1)
  679.     patch->area = 1;
  680.   if (newp->area <= 1)
  681.     newp->area = 1;
  682.  
  683.   WindingCenter(patch->winding, patch->origin);
  684.   VectorAdd(patch->origin, patch->plane->normal, patch->origin);
  685.   leaf = &bspMem->shared.quake1.dleafs[PointInLeafNum(bspMem, patch->origin)];
  686.   patch->cluster = leaf->visofs;
  687.  
  688.   WindingCenter(newp->winding, newp->origin);
  689.   VectorAdd(newp->origin, newp->plane->normal, newp->origin);
  690.   leaf = &bspMem->shared.quake1.dleafs[PointInLeafNum(bspMem, newp->origin)];
  691.   newp->cluster = leaf->visofs;
  692. }
  693.  
  694. /*
  695.  * =============
  696.  * SubdividePatch
  697.  * 
  698.  * Chops the patch only if its local bounds exceed the max size
  699.  * =============
  700.  */
  701. void SubdividePatch(__memBase, register struct patch *patch)
  702. {
  703.   struct winding *w, *o1, *o2;
  704.   vec3_t mins, maxs, total;
  705.   vec3_t split;
  706.   vec_t dist;
  707.   int i, j;
  708.   vec_t v;
  709.   struct patch *newp;
  710.  
  711.   w = patch->winding;
  712.   mins[0] = mins[1] = mins[2] = 99999;
  713.   maxs[0] = maxs[1] = maxs[2] = -99999;
  714.   for (i = 0; i < w->numpoints; i++) {
  715.     for (j = 0; j < 3; j++) {
  716.       v = w->points[i][j];
  717.       if (v < mins[j])
  718.     mins[j] = v;
  719.       if (v > maxs[j])
  720.     maxs[j] = v;
  721.     }
  722.   }
  723.   VectorSubtract(maxs, mins, total);
  724.   for (i = 0; i < 3; i++)
  725.     if (total[i] > (subdiv + 1))
  726.       /* no splitting needed */
  727.       return;
  728.  
  729.   /* split the winding */
  730.   VectorClear(split);
  731.   split[i] = 1;
  732.   dist = (mins[i] + maxs[i]) * 0.5;
  733.   ClipWindingEpsilon(w, split, dist, ON_EPSILON, &o1, &o2);
  734.  
  735.   /* create a new patch */
  736.   if (numpatches == MAX_PATCHES)
  737.     Error("MAX_PATCHES\n");
  738.   newp = &patches[numpatches];
  739.   numpatches++;
  740.  
  741.   newp->next = patch->next;
  742.   patch->next = newp;
  743.  
  744.   patch->winding = o1;
  745.   newp->winding = o2;
  746.  
  747.   FinishSplit(bspMem, patch, newp);
  748.  
  749.   SubdividePatch(bspMem, patch);
  750.   SubdividePatch(bspMem, newp);
  751. }
  752.  
  753. /*
  754.  * =============
  755.  * DicePatch
  756.  * 
  757.  * Chops the patch by a global grid
  758.  * =============
  759.  */
  760. void DicePatch(__memBase, register struct patch *patch)
  761. {
  762.   struct winding *w, *o1, *o2;
  763.   vec3_t mins, maxs;
  764.   vec3_t split;
  765.   vec_t dist;
  766.   int i;
  767.   struct patch *newp;
  768.  
  769.   w = patch->winding;
  770.   WindingBounds(w, mins, maxs);
  771.   for (i = 0; i < 3; i++)
  772.     if (floor((mins[i] + 1) / subdiv) < floor((maxs[i] - 1) / subdiv))
  773.       break;
  774.   if (i == 3) {
  775.     /* no splitting needed */
  776.     return;
  777.   }
  778.  
  779.   /* split the winding */
  780.   VectorClear(split);
  781.   split[i] = 1;
  782.   dist = subdiv * (1 + floor((mins[i] + 1) / subdiv));
  783.   ClipWindingEpsilon(w, split, dist, ON_EPSILON, &o1, &o2);
  784.  
  785.   /* create a new patch */
  786.   if (numpatches == MAX_PATCHES)
  787.     Error("MAX_PATCHES\n");
  788.   newp = &patches[numpatches];
  789.   numpatches++;
  790.  
  791.   newp->next = patch->next;
  792.   patch->next = newp;
  793.  
  794.   patch->winding = o1;
  795.   newp->winding = o2;
  796.  
  797.   FinishSplit(bspMem, patch, newp);
  798.  
  799.   DicePatch(bspMem, patch);
  800.   DicePatch(bspMem, newp);
  801. }
  802.  
  803. /*
  804.  * =============
  805.  * SubdividePatches
  806.  * =============
  807.  */
  808. void SubdividePatches(__memBase)
  809. {
  810.   int i, num;
  811.  
  812.   if (subdiv < 1)
  813.     return;
  814.  
  815.   num = numpatches;                        /* because the list will grow */
  816.  
  817.   for (i = 0; i < num; i++)
  818.     /*  SubdividePatch (&patches[i]); */
  819.     DicePatch(bspMem, &patches[i]);
  820.  
  821.   mprintf("%5i patches after subdivision\n", numpatches);
  822. }
  823.  
  824. /*
  825.  * ================
  826.  * CalcFaceExtents
  827.  * 
  828.  * Fills in s->texmins[] and s->texsize[]
  829.  * also sets exactmins[] and exactmaxs[]
  830.  * ================
  831.  */
  832. void CalcFaceExtentsII(__memBase, register struct lightinfo *l)
  833. {
  834.   struct dface_t *s;
  835.   vec_t mins[2], maxs[2], val;
  836.   int i, j, e;
  837.   struct dvertex_t *v;
  838.   struct texinfo *tex;
  839.   vec3_t vt;
  840.  
  841.   s = l->face;
  842.  
  843.   mins[0] = mins[1] = 999999;
  844.   maxs[0] = maxs[1] = -99999;
  845.  
  846.   tex = &bspMem->shared.quake1.texinfo[s->texinfo];
  847.  
  848.   for (i = 0; i < s->numedges; i++) {
  849.     e = bspMem->shared.quake1.dsurfedges[s->firstedge + i];
  850.     if (e >= 0)
  851.       v = bspMem->shared.quake1.dvertexes + bspMem->shared.quake1.dedges[e].v[0];
  852.     else
  853.       v = bspMem->shared.quake1.dvertexes + bspMem->shared.quake1.dedges[-e].v[1];
  854.  
  855. /*  VectorAdd (v->point, l->modelorg, vt); */
  856.     VectorCopy(v->point, vt);
  857.  
  858.     for (j = 0; j < 2; j++) {
  859.       val = DotProduct(vt, tex->vecs[j]) + tex->vecs[j][3];
  860.       if (val < mins[j])
  861.     mins[j] = val;
  862.       if (val > maxs[j])
  863.     maxs[j] = val;
  864.     }
  865.   }
  866.  
  867.   for (i = 0; i < 2; i++) {
  868.     l->exactmins[i] = mins[i];
  869.     l->exactmaxs[i] = maxs[i];
  870.  
  871.     mins[i] = floor(mins[i] / 16);
  872.     maxs[i] = ceil(maxs[i] / 16);
  873.  
  874.     l->texmins[i] = mins[i];
  875.     l->texsize[i] = maxs[i] - mins[i];
  876.  
  877.     if (l->texsize[0] * l->texsize[1] > SINGLEMAP / 4)        /* div 4 for extrasamples */
  878.       eprintf("Surface to large to map: %d*%d", l->texsize[0], l->texsize[1]);
  879.   }
  880. }
  881.  
  882. /*
  883.  * =================================================================
  884.  * 
  885.  * LIGHTMAP SAMPLE GENERATION
  886.  * 
  887.  * =================================================================
  888.  */
  889.  
  890. #define    ANGLE_UP    -1
  891. #define    ANGLE_DOWN    -2
  892.  
  893. /*
  894.  * =============
  895.  * CreateDirectLights
  896.  * =============
  897.  */
  898. void CreateDirectLights(__memBase)
  899. {
  900.   int i;
  901.   struct patch *p;
  902.   struct directlight *dl;
  903.   struct dleaf_t *leaf;
  904.   int cluster;
  905.   struct entity *e, *e2;
  906.   float angle;
  907.   char *_color;
  908.   float intensity;
  909.  
  910.   /* surfaces */
  911.   for (i = 0, p = patches; i < numpatches; i++, p++) {
  912.     if (p->totallight[0] < DIRECT_LIGHT
  913.     && p->totallight[1] < DIRECT_LIGHT
  914.     && p->totallight[2] < DIRECT_LIGHT)
  915.       continue;
  916.  
  917.     if (!(dl = (struct directlight *)tmalloc(sizeof(struct directlight))))
  918.         Error(failed_memoryunsize, "directlight");
  919.  
  920.     numdlights++;
  921.  
  922.     VectorCopy(p->origin, dl->origin);
  923.  
  924.     leaf = &bspMem->shared.quake1.dleafs[PointInLeafNum(bspMem, dl->origin)];
  925.     cluster = leaf->visofs;
  926.     dl->next = directlights[cluster];
  927.     directlights[cluster] = dl;
  928.  
  929.     dl->type = emit_surface;
  930.     VectorCopy(p->plane->normal, dl->normal);
  931.  
  932.     dl->intensity = ColorNormalize(p->totallight, dl->color);
  933.     dl->intensity *= p->area * direct_scale;
  934.     VectorClear(p->totallight);                    /* all sent now */
  935.   }
  936.  
  937.   /* entities */
  938.   for (i = 0; i < bspMem->nummapentities; i++) {
  939.     e = &bspMem->mapentities[i];
  940.     if (strncmp(e->classname, "light", 5))
  941.       continue;
  942.  
  943.     if (!(dl = (struct directlight *)tmalloc(sizeof(struct directlight))))
  944.         Error(failed_memoryunsize, "directlight");
  945.  
  946.     numdlights++;
  947.  
  948.     VectorCopy(e->origin, dl->origin);
  949.     dl->style = e->style;
  950.  
  951.     leaf = &bspMem->shared.quake1.dleafs[PointInLeafNum(bspMem, dl->origin)];
  952.     cluster = leaf->visofs;
  953.     dl->next = directlights[cluster];
  954.     directlights[cluster] = dl;
  955.  
  956.     intensity = e->light;
  957.     _color = ValueForKey(e, "_color");
  958.     if (_color && _color[1]) {
  959.       sscanf(_color, "%g %g %g", &dl->color[0], &dl->color[1], &dl->color[2]);
  960.       ColorNormalize(dl->color, dl->color);
  961.     }
  962.     else
  963.       dl->color[0] = dl->color[1] = dl->color[2] = 1.0;
  964.     dl->intensity = intensity * entity_scale;
  965.     dl->type = emit_point;
  966.  
  967.     if (e->target || !strcmp(e->target, "light_spot")) {
  968.       dl->type = emit_spotlight;
  969.       dl->stopdot = FloatForKey(e, "_cone");
  970.       if (!dl->stopdot)
  971.     dl->stopdot = 10;
  972.       dl->stopdot = cos(dl->stopdot / 180 * 3.14159);
  973.       if (e->target[0]) {                    /* point towards target */
  974.     if (!(e2 = e->targetent))
  975.       eprintf("light at (%g %g %g) has missing target\n",
  976.           dl->origin[0], dl->origin[1], dl->origin[2]);
  977.     else {
  978.       VectorSubtract(e2->origin, dl->origin, dl->normal);
  979.       VectorNormalize(dl->normal);
  980.     }
  981.       }
  982.       else {                            /* point down angle */
  983.     angle = e->angle;
  984.     if (angle == ANGLE_UP) {
  985.       dl->normal[0] = dl->normal[1] = 0;
  986.       dl->normal[2] = 1;
  987.     }
  988.     else if (angle == ANGLE_DOWN) {
  989.       dl->normal[0] = dl->normal[1] = 0;
  990.       dl->normal[2] = -1;
  991.     }
  992.     else {
  993.       dl->normal[2] = 0;
  994.       dl->normal[0] = cos(angle / 180 * 3.14159);
  995.       dl->normal[1] = sin(angle / 180 * 3.14159);
  996.     }
  997.       }
  998.     }
  999.   }
  1000.  
  1001.   mprintf("%5i direct lights\n", numdlights);
  1002. }
  1003.  
  1004. /*
  1005.  * =============
  1006.  * AddSampleToPatch
  1007.  * 
  1008.  * Take the sample's collected light and
  1009.  * add it back into the apropriate patch
  1010.  * for the radiosity pass.
  1011.  * 
  1012.  * The sample is added to all patches that might include
  1013.  * any part of it.  They are counted and averaged, so it
  1014.  * doesn't generate extra light.
  1015.  * =============
  1016.  */
  1017. void AddSampleToPatch(vec3_t pos, vec3_t color, register int facenum)
  1018. {
  1019.   struct patch *patch;
  1020.   vec3_t mins, maxs;
  1021.   int i;
  1022.  
  1023.   if (numbounce == 0)
  1024.     return;
  1025.   if (color[0] + color[1] + color[2] < 3)
  1026.     return;
  1027.  
  1028.   for (patch = facepatches[facenum]; patch; patch = patch->next) {
  1029.     /* see if the point is in this patch (roughly) */
  1030.     WindingBounds(patch->winding, mins, maxs);
  1031.     for (i = 0; i < 3; i++) {
  1032.       if (mins[i] > pos[i] + 16)
  1033.     goto nextpatch;
  1034.       if (maxs[i] < pos[i] - 16)
  1035.     goto nextpatch;
  1036.     }
  1037.  
  1038.     /* add the sample to the patch */
  1039.     patch->samples++;
  1040.     VectorAdd(patch->samplelight, color, patch->samplelight);
  1041.   nextpatch:;
  1042.   }
  1043. }
  1044.  
  1045. /*
  1046.  * =================================================================
  1047.  * 
  1048.  * POINT TRIANGULATION
  1049.  * 
  1050.  * =================================================================
  1051.  */
  1052.  
  1053. struct edgeshare {
  1054.   struct dface_t *faces[2];
  1055.   bool coplanar;
  1056. };
  1057.  
  1058. int *facelinks;                            /*[MAX_MAP_FACES]; */
  1059. int *planelinks[2];                        /*[MAX_MAP_PLANES]; */
  1060.  
  1061. /*
  1062.  * ============
  1063.  * LinkPlaneFaces
  1064.  * ============
  1065.  */
  1066. void LinkPlaneFaces(__memBase)
  1067. {
  1068.   int i;
  1069.   struct dface_t *f;
  1070.  
  1071.   if (!(facelinks = (int *)kmalloc(bspMem->shared.quake1.numfaces * sizeof(int))))
  1072.       Error(failed_memoryunsize, "facelinks");
  1073.   if (!(planelinks[0] = (int *)kmalloc(bspMem->shared.quake1.numplanes * sizeof(int))))
  1074.       Error(failed_memoryunsize, "planelinks[0]");
  1075.   if (!(planelinks[1] = (int *)kmalloc(bspMem->shared.quake1.numplanes * sizeof(int))))
  1076.       Error(failed_memoryunsize, "planelinks[1]");
  1077.  
  1078.   f = bspMem->shared.quake1.dfaces;
  1079.   for (i = 0; i < bspMem->shared.quake1.numfaces; i++, f++) {
  1080.     facelinks[i] = planelinks[f->side][f->planenum];
  1081.     planelinks[f->side][f->planenum] = i;
  1082.   }
  1083. }
  1084.  
  1085. /*
  1086.  * ============
  1087.  * PairEdges
  1088.  * ============
  1089.  */
  1090. void PairEdges(__memBase)
  1091. {
  1092.   int i, j, k;
  1093.   struct dface_t *f;
  1094.   struct edgeshare *e;
  1095.   struct edgeshare *edgeshare;
  1096.  
  1097.   if (!(edgeshare = (struct edgeshare *)tmalloc(bspMem->shared.quake1.numedges * sizeof(struct edgeshare))))
  1098.       Error(failed_memoryunsize, "edgeshare");
  1099.  
  1100.   f = bspMem->shared.quake1.dfaces;
  1101.   for (i = 0; i < bspMem->shared.quake1.numfaces; i++, f++) {
  1102.     for (j = 0; j < f->numedges; j++) {
  1103.       k = bspMem->shared.quake1.dsurfedges[f->firstedge + j];
  1104.       if (k < 0) {
  1105.     e = &edgeshare[-k];
  1106.     e->faces[1] = f;
  1107.       }
  1108.       else {
  1109.     e = &edgeshare[k];
  1110.     e->faces[0] = f;
  1111.       }
  1112.  
  1113.       if (e->faces[0] && e->faces[1]) {
  1114.     /* determine if coplanar */
  1115.     if (e->faces[0]->planenum == e->faces[1]->planenum)
  1116.       e->coplanar = TRUE;
  1117.       }
  1118.     }
  1119.   }
  1120.  
  1121.   tfree(edgeshare);
  1122. }
  1123.  
  1124. /*
  1125.  * ===============
  1126.  * AllocTriangulation
  1127.  * ===============
  1128.  */
  1129. struct triangulation *AllocTriangulation(register struct dplane_t *plane)
  1130. {
  1131.   struct triangulation *t;
  1132.   if (!(t = (struct triangulation *)tmalloc(sizeof(struct triangulation))))
  1133.       Error(failed_memoryunsize, "triangulation");
  1134.  
  1135.   t->plane = plane;
  1136.   return t;
  1137. }
  1138.  
  1139. /*
  1140.  * ===============
  1141.  * FreeTriangulation
  1142.  * ===============
  1143.  */
  1144. void FreeTriangulation(register struct triangulation *trian)
  1145. {
  1146.   if (trian->matrixsquare)
  1147.     tfree(trian->edgematrix);
  1148.   if (trian->numedges)
  1149.     tfree(trian->edges);
  1150.   if (trian->numpoints)
  1151.     tfree(trian->points);
  1152.   if (trian->numtris)
  1153.     tfree(trian->tris);
  1154.   tfree(trian);
  1155. }
  1156.  
  1157. struct triedge *FindTriEdge(register struct triangulation *trian, register int p0, register int p1)
  1158. {
  1159.   struct triedge *e, *be;
  1160.   vec3_t v1;
  1161.   vec3_t normal;
  1162.   vec_t dist;
  1163.  
  1164.   /* recalculation */
  1165.   if ((trian->matrixsquare < p0) || (trian->matrixsquare < p1)) {
  1166.     struct triedge **newtrie;
  1167.     int i, newsquare = p0 > p1 ? p0 : p1;
  1168.     unsigned char *new, *old;
  1169.  
  1170.     if (!(newtrie = (struct triedge **)tmalloc(newsquare * newsquare * sizeof(struct triedge *))))
  1171.         Error(failed_memoryunsize, "triedges");
  1172.  
  1173.     new = (unsigned char *)newtrie;
  1174.     old = (unsigned char *)trian->edgematrix;
  1175.  
  1176.     for (i = 0; i < trian->matrixsquare; i++) {
  1177.       __memcpy(new + (i * newsquare), old + (i * trian->matrixsquare), trian->matrixsquare * sizeof(struct triedge *));
  1178.     }
  1179.  
  1180.     tfree(trian->edgematrix);
  1181.     trian->edgematrix = newtrie;
  1182.     trian->matrixsquare = newsquare;
  1183.   }
  1184.   else if (trian->edgematrix[(p0 * trian->matrixsquare) + p1])
  1185.     return trian->edgematrix[(p0 * trian->matrixsquare) + p1];
  1186.  
  1187.   if (trian->numedges > MAX_TRI_EDGES - 2)
  1188.     Error("trian->numedges > MAX_TRI_EDGES-2");
  1189.  
  1190.   VectorSubtract(trian->points[p1]->origin, trian->points[p0]->origin, v1);
  1191.   VectorNormalize(v1);
  1192.   CrossProduct(v1, trian->plane->normal, normal);
  1193.   dist = DotProduct(trian->points[p0]->origin, normal);
  1194.  
  1195.   if (!(trian->edges = (struct triedge *)trealloc(trian->edges, (trian->numedges + 2) * sizeof(struct triedge))))
  1196.       Error(failed_memoryunsize, "triedges");
  1197.  
  1198.   e = &trian->edges[trian->numedges];
  1199.   e->p0 = p0;
  1200.   e->p1 = p1;
  1201.   e->tri = NULL;
  1202.   VectorCopy(normal, e->normal);
  1203.   e->dist = dist;
  1204.   trian->numedges++;
  1205.   trian->edgematrix[(p0 * trian->matrixsquare) + p1] = e;
  1206.  
  1207.   be = &trian->edges[trian->numedges];
  1208.   be->p0 = p1;
  1209.   be->p1 = p0;
  1210.   be->tri = NULL;
  1211.   VectorNegateTo(normal, be->normal);
  1212.   be->dist = -dist;
  1213.   trian->numedges++;
  1214.   trian->edgematrix[(p1 * trian->matrixsquare) + p0] = be;
  1215.  
  1216.   return e;
  1217. }
  1218.  
  1219. struct tripoly *AllocTriangle(register struct triangulation *trian)
  1220. {
  1221.   if (!(trian->tris = (struct tripoly *)trealloc(trian->tris, ++trian->numtris * sizeof(struct tripoly))))
  1222.       Error(failed_memoryunsize, "triangle");
  1223.  
  1224.   return trian->tris + trian->numtris - 1;
  1225. }
  1226.  
  1227. /*
  1228.  * ============
  1229.  * TriEdge_r
  1230.  * ============
  1231.  */
  1232. void TriEdge_r(register struct triangulation *trian, register struct triedge *e)
  1233. {
  1234.   int i, bestp = 0;
  1235.   vec3_t v1, v2;
  1236.   vec_t *p0, *p1, *p;
  1237.   vec_t best, ang;
  1238.   struct tripoly *nt;
  1239.  
  1240.   if (e->tri)
  1241.     return;                            /* allready connected by someone */
  1242.  
  1243.   /* find the point with the best angle */
  1244.   p0 = trian->points[e->p0]->origin;
  1245.   p1 = trian->points[e->p1]->origin;
  1246.   best = 1.1;
  1247.   for (i = 0; i < trian->numpoints; i++) {
  1248.     p = trian->points[i]->origin;
  1249.     /* a 0 dist will form a degenerate triangle */
  1250.     if (DotProduct(p, e->normal) - e->dist < 0)
  1251.       continue;                            /* behind edge */
  1252.  
  1253.     VectorSubtract(p0, p, v1);
  1254.     VectorSubtract(p1, p, v2);
  1255.     if (!VectorNormalize(v1))
  1256.       continue;
  1257.     if (!VectorNormalize(v2))
  1258.       continue;
  1259.     ang = DotProduct(v1, v2);
  1260.     if (ang < best) {
  1261.       best = ang;
  1262.       bestp = i;
  1263.     }
  1264.   }
  1265.   if (best >= 1)
  1266.     return;                            /* edge doesn't match anything */
  1267.  
  1268.   /* make a new triangle */
  1269.   nt = AllocTriangle(trian);
  1270.   nt->edges[0] = e;
  1271.   nt->edges[1] = FindTriEdge(trian, e->p1, bestp);
  1272.   nt->edges[2] = FindTriEdge(trian, bestp, e->p0);
  1273.   for (i = 0; i < 3; i++)
  1274.     nt->edges[i]->tri = nt;
  1275.   TriEdge_r(trian, FindTriEdge(trian, bestp, e->p1));
  1276.   TriEdge_r(trian, FindTriEdge(trian, e->p0, bestp));
  1277. }
  1278.  
  1279. /*
  1280.  * ============
  1281.  * TriangulatePoints
  1282.  * ============
  1283.  */
  1284. void TriangulatePoints(register struct triangulation *trian)
  1285. {
  1286.   vec_t d, bestd;
  1287.   vec3_t v1;
  1288.   int bp1 = 0, bp2 = 0, i, j;
  1289.   vec_t *p1, *p2;
  1290.   struct triedge *e, *e2;
  1291.  
  1292.   if (trian->numpoints < 2)
  1293.     return;
  1294.  
  1295.   /* find the two closest points */
  1296.   bestd = 9999;
  1297.   for (i = 0; i < trian->numpoints; i++) {
  1298.     p1 = trian->points[i]->origin;
  1299.     for (j = i + 1; j < trian->numpoints; j++) {
  1300.       p2 = trian->points[j]->origin;
  1301.       VectorSubtract(p2, p1, v1);
  1302.       d = VectorLength(v1);
  1303.       if (d < bestd) {
  1304.     bestd = d;
  1305.     bp1 = i;
  1306.     bp2 = j;
  1307.       }
  1308.     }
  1309.   }
  1310.  
  1311.   e = FindTriEdge(trian, bp1, bp2);
  1312.   e2 = FindTriEdge(trian, bp2, bp1);
  1313.   TriEdge_r(trian, e);
  1314.   TriEdge_r(trian, e2);
  1315. }
  1316.  
  1317. /*
  1318.  * ===============
  1319.  * AddPointToTriangulation
  1320.  * ===============
  1321.  */
  1322. void AddPointToTriangulation(register struct patch *patch, register struct triangulation *trian)
  1323. {
  1324.   if (!(trian->points = (struct patch **)trealloc(trian->points, ++trian->numpoints * sizeof(struct patch *))))
  1325.       Error(failed_memoryunsize, "point");
  1326.  
  1327.   trian->points[trian->numpoints - 1] = patch;
  1328. }
  1329.  
  1330. /*
  1331.  * ===============
  1332.  * LerpTriangle
  1333.  * ===============
  1334.  */
  1335. void LerpTriangle(register struct triangulation *trian, register struct tripoly *t, vec3_t point, vec3_t color)
  1336. {
  1337.   struct patch *p1, *p2, *p3;
  1338.   vec3_t base, d1, d2;
  1339.   float x, y, x1, y1, x2, y2;
  1340.  
  1341.   p1 = trian->points[t->edges[0]->p0];
  1342.   p2 = trian->points[t->edges[1]->p0];
  1343.   p3 = trian->points[t->edges[2]->p0];
  1344.  
  1345.   VectorCopy(p1->totallight, base);
  1346.   VectorSubtract(p2->totallight, base, d1);
  1347.   VectorSubtract(p3->totallight, base, d2);
  1348.  
  1349.   x = DotProduct(point, t->edges[0]->normal) - t->edges[0]->dist;
  1350.   y = DotProduct(point, t->edges[2]->normal) - t->edges[2]->dist;
  1351.  
  1352.   x1 = 0;
  1353.   y1 = DotProduct(p2->origin, t->edges[2]->normal) - t->edges[2]->dist;
  1354.  
  1355.   x2 = DotProduct(p3->origin, t->edges[0]->normal) - t->edges[0]->dist;
  1356.   y2 = 0;
  1357.  
  1358.   if (fabs(y1) < ON_EPSILON || fabs(x2) < ON_EPSILON) {
  1359.     VectorCopy(base, color);
  1360.     return;
  1361.   }
  1362.  
  1363.   VectorMA(base, x / x2, d2, color);
  1364.   VectorMA(color, y / y1, d1, color);
  1365. }
  1366.  
  1367. bool PointInTriangle(vec3_t point, register struct tripoly * t)
  1368. {
  1369.   int i;
  1370.   struct triedge *e;
  1371.   vec_t d;
  1372.  
  1373.   for (i = 0; i < 3; i++) {
  1374.     e = t->edges[i];
  1375.     d = DotProduct(e->normal, point) - e->dist;
  1376.     if (d < 0)
  1377.       return FALSE;                        /* not inside */
  1378.  
  1379.   }
  1380.  
  1381.   return TRUE;
  1382. }
  1383.  
  1384. /*
  1385.  * ===============
  1386.  * SampleTriangulation
  1387.  * ===============
  1388.  */
  1389. void SampleTriangulation(vec3_t point, register struct triangulation *trian, vec3_t color)
  1390. {
  1391.   struct tripoly *t;
  1392.   struct triedge *e;
  1393.   vec_t d, best;
  1394.   struct patch *p0, *p1;
  1395.   vec3_t v1, v2;
  1396.   int i, j;
  1397.  
  1398.   if (trian->numpoints == 0) {
  1399.     VectorClear(color);
  1400.     return;
  1401.   }
  1402.   if (trian->numpoints == 1) {
  1403.     VectorCopy(trian->points[0]->totallight, color);
  1404.     return;
  1405.   }
  1406.  
  1407.   /* search for triangles */
  1408.   for (t = trian->tris, j = 0; j < trian->numtris; t++, j++) {
  1409.     if (!PointInTriangle(point, t))
  1410.       continue;
  1411.  
  1412.     /* this is it */
  1413.     LerpTriangle(trian, t, point, color);
  1414.     return;
  1415.   }
  1416.  
  1417.   /* search for exterior edge */
  1418.   for (e = trian->edges, j = 0; j < trian->numedges; e++, j++) {
  1419.     if (e->tri)
  1420.       continue;                            /* not an exterior edge */
  1421.  
  1422.     d = DotProduct(point, e->normal) - e->dist;
  1423.     if (d < 0)
  1424.       continue;                            /* not in front of edge */
  1425.  
  1426.     p0 = trian->points[e->p0];
  1427.     p1 = trian->points[e->p1];
  1428.  
  1429.     VectorSubtract(p1->origin, p0->origin, v1);
  1430.     VectorNormalize(v1);
  1431.     VectorSubtract(point, p0->origin, v2);
  1432.     d = DotProduct(v2, v1);
  1433.     if (d < 0)
  1434.       continue;
  1435.     if (d > 1)
  1436.       continue;
  1437.     for (i = 0; i < 3; i++)
  1438.       color[i] = p0->totallight[i] + d * (p1->totallight[i] - p0->totallight[i]);
  1439.     return;
  1440.   }
  1441.  
  1442.   /* search for nearest point */
  1443.   best = 99999;
  1444.   p1 = NULL;
  1445.   for (j = 0; j < trian->numpoints; j++) {
  1446.     p0 = trian->points[j];
  1447.     VectorSubtract(point, p0->origin, v1);
  1448.     d = VectorLength(v1);
  1449.     if (d < best) {
  1450.       best = d;
  1451.       p1 = p0;
  1452.     }
  1453.   }
  1454.  
  1455.   if (!p1)
  1456.     Error("SampleTriangulation: no points");
  1457.  
  1458.   VectorCopy(p1->totallight, color);
  1459. }
  1460.  
  1461. /*
  1462.  * =============
  1463.  * GatherSampleLight
  1464.  * 
  1465.  * Lightscale is the normalizer for multisampling
  1466.  * =============
  1467.  */
  1468. void GatherSampleLight(__memBase, vec3_t pos, vec3_t normal,
  1469.                register float **styletable, register int offset, register int mapsize, register float lightscale)
  1470. {
  1471.   int i;
  1472.   struct directlight *l;
  1473.   unsigned char pvs[(MAX_MAP_LEAFS + 7) / 8];
  1474.   vec3_t delta;
  1475.   float dot, dot2;
  1476.   float dist;
  1477.   float scale = 1.0;
  1478.   float *dest;
  1479.  
  1480.   /* get the PVS for the pos to limit the number of checks */
  1481.   if (!PvsForOrigin(bspMem, pos, pvs)) {
  1482.     return;
  1483.   }
  1484.  
  1485.   for (i = 0; i < bspMem->shared.quake1.numleafs; i++) {
  1486.     if ((pvs[i >> 3] & (1 << (i & 7)))) {
  1487.       for (l = directlights[i]; l; l = l->next) {
  1488.     VectorSubtract(l->origin, pos, delta);
  1489.     dist = VectorNormalize(delta);
  1490.     dot = DotProduct(delta, normal);
  1491.     if (dot <= 0.001)
  1492.       continue;                        /* behind sample surface */
  1493.     switch (l->type) {
  1494.       case emit_point:
  1495.         /* linear falloff */
  1496.         scale = (l->intensity - dist) * dot;
  1497.         break;
  1498.  
  1499.       case emit_surface:
  1500.         dot2 = -DotProduct(delta, l->normal);
  1501.         if (dot2 <= 0.001)
  1502.           goto skipadd;                    /* behind light surface */
  1503.         scale = (l->intensity / (dist * dist)) * dot * dot2;
  1504.         break;
  1505.  
  1506.       case emit_spotlight:
  1507.         /* linear falloff */
  1508.         dot2 = -DotProduct(delta, l->normal);
  1509.         if (dot2 <= l->stopdot)
  1510.           goto skipadd;                    /* outside light cone */
  1511.         scale = (l->intensity - dist) * dot;
  1512.         break;
  1513.       default:
  1514.         Error("Bad l->type");
  1515.     }
  1516.  
  1517.     if (TestLine_r(0, pos, l->origin))
  1518.       continue;                        /* occluded */
  1519.     if (scale <= 0)
  1520.       continue;
  1521.  
  1522.     /* if this style doesn't have a table yet, allocate one */
  1523.     if (!styletable[l->style])
  1524.       styletable[l->style] = (float *)tmalloc(mapsize);
  1525.  
  1526.     dest = styletable[l->style] + offset;
  1527.     /* add some light to it */
  1528.     VectorMA(dest, scale * lightscale, l->color, dest);
  1529.  
  1530.       skipadd:;
  1531.       }
  1532.     }
  1533. /** mprogress(bspMem->shared.quake1.numleafs, i + 1); **/
  1534.   }
  1535.  
  1536. }
  1537.  
  1538. /*
  1539.  * =============
  1540.  * FinalLightFace
  1541.  * 
  1542.  * Add the indirect lighting on top of the direct
  1543.  * lighting and save into final map format
  1544.  * =============
  1545.  */
  1546. void FinalLightFace(__memBase, register int facenum)
  1547. {
  1548.   struct dface_t *f;
  1549.   int i, j, k, st;
  1550.   vec3_t lb;
  1551.   struct patch *patch;
  1552.   struct triangulation *trian = 0;
  1553.   struct facelight *fl;
  1554.   float minlight;
  1555.   float max, newmax;
  1556.   unsigned char *dest;
  1557.   int pfacenum;
  1558.   vec3_t facemins, facemaxs;
  1559.  
  1560.   f = &bspMem->shared.quake1.dfaces[facenum];
  1561.   fl = &facelights[facenum];
  1562.  
  1563.   if ((bspMem->shared.quake1.texinfo[f->texinfo].flags & TEX_SPECIAL)) {    /* non-lit texture */
  1564.     if (bspMem->litOptions & LIGHT_WATERLIT) {
  1565.       int *textures = (int *)(bspMem->shared.quake1.dtexdata + 4);
  1566.       struct mipmap *tex = (struct mipmap *)(bspMem->shared.quake1.dtexdata + textures[bspMem->shared.quake1.texinfo[f->texinfo].miptex]);
  1567.  
  1568.       if (!__strcmp(tex->name, "sky"))
  1569.     return;
  1570.     }
  1571.     else
  1572.       return;
  1573.   }
  1574.  
  1575.   if (bspMem->shared.quake1.lightdatasize + (fl->numstyles * (fl->numsamples * 3)) >= bspMem->shared.quake1.max_lightdatasize)
  1576.     ExpandClusters(bspMem, LUMP_LIGHTING);
  1577.   f->lightofs = bspMem->shared.quake1.lightdatasize;
  1578.   bspMem->shared.quake1.lightdatasize += fl->numstyles * (fl->numsamples * 3);
  1579.  
  1580.   f->styles[0] = 0;
  1581.   f->styles[1] = f->styles[2] = f->styles[3] = 0xff;
  1582.  
  1583.   /* set up the triangulation */
  1584.   if (numbounce > 0) {
  1585.     ClearLBounds(facemins, facemaxs);
  1586.     for (i = 0; i < f->numedges; i++) {
  1587.       int ednum = bspMem->shared.quake1.dsurfedges[f->firstedge + i];
  1588.  
  1589.       if (ednum >= 0)
  1590.     AddPointToBounds(bspMem->shared.quake1.dvertexes[bspMem->shared.quake1.dedges[ednum].v[0]].point, facemins, facemaxs);
  1591.       else
  1592.     AddPointToBounds(bspMem->shared.quake1.dvertexes[bspMem->shared.quake1.dedges[-ednum].v[1]].point, facemins, facemaxs);
  1593.     }
  1594.  
  1595.     trian = AllocTriangulation(&bspMem->shared.quake1.dplanes[f->planenum]);
  1596.  
  1597.     /*
  1598.      * for all faces on the plane, add the nearby patches
  1599.      * to the triangulation
  1600.      */
  1601.     for (pfacenum = planelinks[f->side][f->planenum];
  1602.      pfacenum; pfacenum = facelinks[pfacenum]) {
  1603.       for (patch = facepatches[pfacenum]; patch; patch = patch->next) {
  1604.     for (i = 0; i < 3; i++) {
  1605.       if (facemins[i] - patch->origin[i] > subdiv * 2)
  1606.         break;
  1607.       if (patch->origin[i] - facemaxs[i] > subdiv * 2)
  1608.         break;
  1609.     }
  1610.     if (i != 3)
  1611.       continue;                        /* not needed for this face */
  1612.     AddPointToTriangulation(patch, trian);
  1613.       }
  1614.     }
  1615. #if 0
  1616.     for (i = 0; i < trian->numpoints; i++)
  1617.       __bzero(trian->edgematrix[i], trian->numpoints * sizeof(trian->edgematrix[0][0]));
  1618. #endif
  1619.     TriangulatePoints(trian);
  1620.   }
  1621.  
  1622.   /*
  1623.    * sample the triangulation
  1624.    *
  1625.    * _minlight allows models that have faces that would not be
  1626.    * illuminated to receive a mottled light pattern instead of
  1627.    * black
  1628.    */
  1629.   minlight = FloatForKey(faceentity[facenum], "_minlight") * 128;
  1630.  
  1631.   dest = &bspMem->shared.quake1.dlightdata[f->lightofs];
  1632.  
  1633.   if (fl->numstyles > MAXLIGHTMAPS) {
  1634.     fl->numstyles = MAXLIGHTMAPS;
  1635.     eprintf("face with too many lightstyles: (%g %g %g)\n",
  1636.         facepatches[facenum]->origin[0],
  1637.         facepatches[facenum]->origin[1],
  1638.         facepatches[facenum]->origin[2]);
  1639.   }
  1640.  
  1641.   for (st = 0; st < fl->numstyles; st++) {
  1642.     f->styles[st] = fl->stylenums[st];
  1643.     for (j = 0; j < fl->numsamples; j++) {
  1644.       VectorCopy((fl->samples[st] + j * 3), lb);
  1645.       if (numbounce > 0 && st == 0) {
  1646.     vec3_t add;
  1647.  
  1648.     SampleTriangulation(fl->origins + j * 3, trian, add);
  1649.     VectorAdd(lb, add, lb);
  1650.       }
  1651.       /* add an ambient term if desired */
  1652.       lb[0] += ambient;
  1653.       lb[1] += ambient;
  1654.       lb[2] += ambient;
  1655.  
  1656.       VectorScale(lb, lightscale, lb);
  1657.  
  1658.       /* we need to clamp without allowing hue to change */
  1659.       for (k = 0; k < 3; k++)
  1660.     if (lb[k] < 1)
  1661.       lb[k] = 1;
  1662.       max = lb[0];
  1663.       if (lb[1] > max)
  1664.     max = lb[1];
  1665.       if (lb[2] > max)
  1666.     max = lb[2];
  1667.       newmax = max;
  1668.       if (newmax < 0)
  1669.     newmax = 0;                        /* roundoff problems */
  1670.  
  1671.       if (newmax < minlight) {
  1672.     newmax = minlight + (rand() % 48);
  1673.       }
  1674.       if (newmax > maxlight)
  1675.     newmax = maxlight;
  1676.  
  1677.       for (k = 0; k < 3; k++) {
  1678.     *dest++ = lb[k] * newmax / max;
  1679.       }
  1680.     }
  1681.   }
  1682.  
  1683.   if (numbounce > 0)
  1684.     FreeTriangulation(trian);
  1685. }
  1686.  
  1687. /*
  1688.  * =============
  1689.  * RadFace
  1690.  * =============
  1691.  */
  1692. float sampleofs[5][2] =
  1693. {
  1694.   {0, 0},
  1695.   {-0.25, -0.25},
  1696.   {0.25, -0.25},
  1697.   {0.25, 0.25},
  1698.   {-0.25, 0.25}};
  1699.  
  1700. void RadFace(__memBase, register int facenum)
  1701. {
  1702.   struct dface_t *f;
  1703.   struct lightinfo l[5];
  1704.   float *styletable[MAX_LSTYLES];
  1705.   int i, j;
  1706.   float *spot;
  1707.   struct patch *patch;
  1708.   int numsamples;
  1709.   int tablesize;
  1710.   struct facelight *fl;
  1711.  
  1712.   f = &bspMem->shared.quake1.dfaces[facenum];
  1713.  
  1714.   if ((bspMem->shared.quake1.texinfo[f->texinfo].flags & TEX_SPECIAL)) {    /* non-lit texture */
  1715.     if (bspMem->litOptions & LIGHT_WATERLIT) {
  1716.       int *textures = (int *)(bspMem->shared.quake1.dtexdata + 4);
  1717.       struct mipmap *tex = (struct mipmap *)(bspMem->shared.quake1.dtexdata + textures[bspMem->shared.quake1.texinfo[f->texinfo].miptex]);
  1718.  
  1719.       if (!__strcmp(tex->name, "sky"))
  1720.     return;
  1721.     }
  1722.     else
  1723.       return;
  1724.   }
  1725.   __bzero(styletable, sizeof(styletable));
  1726.  
  1727.   if (bspMem->litOptions & LIGHT_EXTRA)
  1728.     numsamples = 5;
  1729.   else
  1730.     numsamples = 1;
  1731.  
  1732.   for (i = 0; i < numsamples; i++) {
  1733.     bzero(&l[i], sizeof(l[i]));
  1734.     l[i].surfnum = facenum;
  1735.     l[i].face = f;
  1736.     VectorCopy(bspMem->shared.quake1.dplanes[f->planenum].normal, l[i].facenormal);
  1737.     l[i].facedist = bspMem->shared.quake1.dplanes[f->planenum].dist;
  1738.     if (f->side) {
  1739.       VectorNegate(l[i].facenormal);
  1740.       l[i].facedist = -l[i].facedist;
  1741.     }
  1742.  
  1743.     /* get the origin offset for rotating bmodels */
  1744.     VectorCopy(faceoffset[facenum], l[i].modelorg);
  1745.  
  1746.     CalcFaceVectors(bspMem, &l[i]);
  1747.     CalcFaceExtentsII(bspMem, &l[i]);
  1748.     CalcPoints(bspMem, &l[i], sampleofs[i][0], sampleofs[i][1]);
  1749.   }
  1750.  
  1751.   tablesize = l[0].numsurfpt * sizeof(vec3_t);
  1752.   styletable[0] = (float *)tmalloc(tablesize);
  1753.  
  1754.   fl = &facelights[facenum];
  1755.   fl->numsamples = l[0].numsurfpt;
  1756.   fl->origins = (float *)tmalloc(tablesize);
  1757.   __memcpy(fl->origins, l[0].surfpt, tablesize);
  1758.  
  1759.   for (i = 0; i < l[0].numsurfpt; i++) {
  1760.     for (j = 0; j < numsamples; j++)
  1761.       GatherSampleLight(bspMem, l[j].surfpt[i], l[0].facenormal, styletable, i * 3, tablesize, 1.0 / numsamples);
  1762.     /* contribute the sample to one or more patches */
  1763.     AddSampleToPatch(l[0].surfpt[i], styletable[0] + i * 3, facenum);
  1764.   }
  1765.  
  1766.   /* average up the direct light on each patch for radiosity */
  1767.   for (patch = facepatches[facenum]; patch; patch = patch->next) {
  1768.     if (patch->samples)
  1769.       VectorScale(patch->samplelight, 1.0 / patch->samples, patch->samplelight);
  1770.   }
  1771.  
  1772.   for (i = 0; i < MAX_LSTYLES; i++) {
  1773.     if (!styletable[i])
  1774.       continue;
  1775.     if (fl->numstyles == MAX_STYLES)
  1776.       break;
  1777.     fl->samples[fl->numstyles] = styletable[i];
  1778.     fl->stylenums[fl->numstyles] = i;
  1779.     fl->numstyles++;
  1780.   }
  1781.  
  1782.   /*
  1783.    * the light from DIRECT_LIGHTS is sent out, but the
  1784.    * texture itself should still be full bright
  1785.    */
  1786.   if (facepatches[facenum]->baselight[0] >= DIRECT_LIGHT ||
  1787.       facepatches[facenum]->baselight[1] >= DIRECT_LIGHT ||
  1788.       facepatches[facenum]->baselight[2] >= DIRECT_LIGHT) {
  1789.     spot = fl->samples[0];
  1790.     for (i = 0; i < l[0].numsurfpt; i++, spot += 3)
  1791.       VectorAdd(spot, facepatches[facenum]->baselight, spot);
  1792.   }
  1793. }
  1794.  
  1795. /*
  1796.  * =============
  1797.  * RadWorld
  1798.  * =============
  1799.  */
  1800. void RadWorld(__memBase)
  1801. {
  1802.   int back, i;
  1803.  
  1804.   mprintf("CalcTR\n");
  1805.   CalcTextureReflectivity(bspMem);
  1806.   mprintf("MakeMB\n");
  1807.   MakeBackPlanes(bspMem);
  1808.   mprintf("MakeP\n");
  1809.   MakeParents(bspMem, 0, -1);
  1810.   /* turn each face into a single patch */
  1811.   mprintf("MakePa\n");
  1812.   MakePatches(bspMem);
  1813.   /* subdivide patches to a maximum dimension */
  1814.   mprintf("SubD\n");
  1815.   SubdividePatches(bspMem);
  1816.   mprintf("%5i patches\n", numpatches);
  1817.   /* create directlights out of patches and lights */
  1818.   mprintf("CreateDL\n");
  1819.   CreateDirectLights(bspMem);
  1820.   mprintf("%5i patches\n", numpatches);
  1821.   back = numpatches;
  1822.   for (i = 0; i < bspMem->shared.quake1.numfaces; i++, bspfileface++) {
  1823.     RadFace(bspMem, i);
  1824.     mprogress(bspMem->shared.quake1.numfaces, i + 1);
  1825.   }
  1826.   mprintf("%5i patches: %d\n", numpatches);
  1827.   numpatches = back;
  1828.   mprintf("%5i patches: %d\n", numpatches);
  1829.   if (numbounce > 0) {
  1830.     /* build transfer lists */
  1831.     mprintf("MakeTr\n");
  1832.     for (i = 0; i < numpatches; i++)
  1833.       MakeTransfers(bspMem, i);
  1834.  
  1835.     mprintf("transfer lists: %g megs\n", (float)total_transfer * sizeof(struct transfer) / (1024 * 1024));
  1836.  
  1837.     /* spread light around */
  1838.     mprintf("Bounce\n");
  1839.     BounceLight();
  1840.     mprintf("FreeTr\n");
  1841.     FreeTransfers();
  1842.     mprintf("CheckP\n");
  1843.     CheckPatches();
  1844.   }
  1845.   /* blend bounced light into direct light and save */
  1846.   mprintf("PairEd\n");
  1847.   PairEdges(bspMem);
  1848.   mprintf("LinkPl\n");
  1849.   LinkPlaneFaces(bspMem);
  1850.   bspMem->shared.quake1.lightdatasize = 0;
  1851.   for (i = 0; i < bspMem->shared.quake1.numfaces; i++) {
  1852.     FinalLightFace(bspMem, i);
  1853.     mprogress(bspMem->shared.quake1.numfaces, i + 1);
  1854.   }
  1855. }
  1856.